/**
 * 
 */
package leetCode;

import java.util.Arrays;
import java.util.HashSet;

/**
 * @author zhong
 *
 */
public class FindSmallestLetterGreaterThanTarget {
	public char nextGreatestLetter(char[] letters, char target) {
		int n = letters.length;
		int left = 0, right = n - 1;
		if (letters[n - 1] <= target) {
			return letters[0];
		}
		while (left < right) {
			int mid = left + ((right - left) >> 1);
			if (letters[mid] <= target) {
				left = mid + 1;
			} else {
				if (mid == 0 || letters[mid - 1] <= target) {
					return letters[mid];
				} else {
					right = mid - 1;
				}
			}
		}
		return letters[left];

	}

	public char nextGreatestLetter3(char[] letters, char target) {
		int n = letters.length;
		int left = 0, right = n - 1;
		while (left < right) {
			int mid = left + ((right - left) >> 1);
			if (letters[mid] <= target) {
				left = mid + 1;
			} else {
				right = mid;
			}
		}
		if (letters[left] <= target) {
			return letters[0];
		} else {
			return letters[left];
		}
	}

	public char nextGreatestLetter1(char[] letters, char target) {
		target++;
		int i = Arrays.binarySearch(letters, target);
		if (i < 0) {
			i = -i - 1;
		}
		return i == letters.length ? letters[0] : letters[i];
	}

	public char nextGreatestLetter2(char[] letters, char target) {
		HashSet<Character> set = new HashSet<>(letters.length);
		for (int i = 0; i < letters.length; i++) {
			set.add(letters[i]);
		}
		char[] tmp = new char[set.size()];
		int i = 0;
		for (char c : set) {
			tmp[i++] = c;
		}
		Arrays.sort(tmp);
		int index = Arrays.binarySearch(tmp, target);
		if (index < 0) {
			index = -index - 1;
		} else {
			index++;
		}
		if (index == tmp.length) {
			return tmp[0];
		} else {
			return tmp[index];
		}
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		char[] letters = { 'c', 'f', 'f', 'f', 'j', 'j', 'j' };
		char target = 'f';
		System.out.println(new FindSmallestLetterGreaterThanTarget().nextGreatestLetter(letters, target));
	}

}
